﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace TSP
{
    class TSPSolverBNB : ITSPSolver
    {
        public TSPSolverBNB(List<City> greedyPath)
        {
            bssf = greedyPath;
            bssfCost = (new TSP.ProblemAndSolver.TSPSolution(new ArrayList(greedyPath))).costOfRoute();
        }

        private PriorityQueue<Matrix> queue = new PriorityQueue<Matrix>();
        private double bssfCost = 0;
        private List<City> bssf;
        private City[] input;
        private int maxStored = 0;
        private int createdStates = 0;
        private int statesPruned = 0;
        private TimeSpan runTime;

        public int MaxStored { get { return this.maxStored; } }
        public int CreatedStates { get { return this.createdStates; } }
        public int PrunedStates { get { return this.statesPruned; } }
        public int RunTime { get { return this.runTime.Seconds; } }

        /// <summary>
        /// Solves the TSP problem
        /// </summary>
        /// <param name="input">array of cities</param>
        /// <returns>list of cities in the order that they should be visited</returns>
        public List<City> solveProblem(City[] input)
        {
            maxStored = 0;
            createdStates = 0;
            statesPruned = 0;

            this.input = input;

            //start timer
            DateTime startTime = DateTime.Now;
            DateTime endTime = startTime.AddSeconds(30);
            Matrix initialMatrix = new Matrix(input);
            enqueue(initialMatrix);
            while (queue.Count > 0)
            {
                if (queue.Count > maxStored)
                    maxStored = queue.Count;
                Matrix currentMatrix = queue.Dequeue();
                if (isGreaterThan(currentMatrix.Cost, bssfCost) || currentMatrix.Cost == bssfCost)
                {
                    statesPruned += queue.Count + 1;
                    break;
                }
                else
                    branch(currentMatrix);
                if (endTime.CompareTo(DateTime.Now) < 0)
                    break;
            }
            runTime = DateTime.Now - startTime;
            return bssf;
        }

        /// <summary>
        /// Split the current matrix into two by finding the best edge and including and excluding it
        /// </summary>
        /// <param name="matrix">currend matrix</param>
        private void branch(Matrix matrix)
        {
            Matrix.Edge bestEdge = getBestEdge(matrix);
            enqueue(new Matrix(matrix, bestEdge, false));
            enqueue(new Matrix(matrix, bestEdge, true));
        }

        /// <summary>
        /// Checks if the route is completed and updates bssf accordingly. Prunes costly paths and enqueues the others
        /// </summary>
        /// <param name="matrix"></param>
        private void enqueue(Matrix matrix)
        {
            ++createdStates;
            if (matrix.isCompleted())
            {
                if (isGreaterThan(bssfCost, matrix.Cost))
                {
                    bssf = intsToCities(matrix.getRoute());
                    bssfCost = matrix.Cost;
                }
            }
            else if (isGreaterThan(bssfCost, matrix.Cost))
                queue.Enqueue(matrix, matrix.Cost);
            else
                statesPruned++;
        }

        /// <summary>
        /// Finds the ints associated with the cities
        /// </summary>
        /// <param name="cities">cities in route order</param>
        /// <returns>cities in route order</returns>
        private List<City> intsToCities(List<int> cities)
        {
            List<City> actualCities = new List<City>();
            foreach (int i in cities)
            {
                actualCities.Add(input[i]);
            }
            return actualCities;

        }

        /// <summary>
        /// finds the best edge for branch and bound to include/exclude
        /// </summary>
        /// <param name="matrix">current matrix</param>
        /// <returns>the ideal edge</returns>
        private Matrix.Edge getBestEdge(Matrix matrix)
        {
            List<Matrix.Edge> zeroEdges = matrix.getZeroEdges();
            Matrix.Edge idealEdge = zeroEdges[0];
            double costDiff = getDifference(matrix, idealEdge);
            foreach (Matrix.Edge edge in zeroEdges)
            {
                double tmpCost = getDifference(matrix, edge);
                if (isGreaterThan(tmpCost, costDiff))
                {
                    costDiff = tmpCost;
                    idealEdge = edge;
                }
            }
            return idealEdge;
        }

        // the following three methods are necessary because -1 equals infinity
        private bool isGreaterThan(double a, double b)
        {
            if (a == -1 && b != -1)
                return true;
            else if (b == -1)
                return false;
            else
                return a > b;
        }

        private double getDifference(Matrix matrix, Matrix.Edge edge)
        {
            double costWith = (new Matrix(matrix, edge, true)).Cost;
            double costWithout = (new Matrix(matrix, edge, false)).Cost;
            return subtract(costWithout, costWith);
        }

        private double subtract(double variable, double subtractMe)
        {
            if (variable == -1 && subtractMe == -1)
                return 0;
            else if (variable < 0 || subtractMe < 0)
                return -1;
            else
                return variable - subtractMe;
        }
    }
}
